\documentclass[a4paper,spanish]{article}

\input{preambulo}

\hyphenation{ob-te-ner}

\begin{document}

\input{caratula}

\tableofcontents

\newpage

\section{M'odulo Arbol23}

\subsection*{Ejercicio 1}
\addcontentsline{toc}{subsection}{Ejercicio 1}
Esta funci'on es la an'aloga a \texttt{foldr} para el tipo \texttt{Arbol23}.  
Como \texttt{Arbol23} tiene 3 constructores, toma como par'ametros 3 funciones 
que se aplican dependiendo el caso. Supongamos que el 'arbol es de tipos 
\texttt{a} y \texttt{b}, y que el fold calcula un valor de un tipo \texttt{c}.  
Entonces para \emph{foldear} una hoja se necesita una funci'on de tipo \texttt{a 
->\ c},
pues tiene que tomar el dato almacenado en ella y calcular un resultado.  Para 
\emph{foldear} un nodo interno de dos hijos hace falta una funci'on que de tipo 
\texttt{b ->\ c ->\ c ->\ c}, dado que tiene que tomar el dato del nodo
y el resultado de \emph{foldear} sus sub'arboles izquierdo y derecho (que 
tendr'an tipo \texttt{c}).  An'alogamente, para nodos internos de tres hijos, se 
necesita una funci'on de tipo \texttt{b ->\ b ->\ c ->\ c ->\ c ->\ c}.

\lstinputlisting[linerange=28-33, firstnumber=28]{../Arbol23.hs}

La funci'on \texttt{internos} usa de manera directa \texttt{foldA23}, con lo 
cual el ejemplo para esa funci'on lo es para esta.

\subsection*{Ejercicio 2}
\addcontentsline{toc}{subsection}{Ejercicio 2}
\texttt{hojas} est'a escrita usando directamente un fold. La funci'on que 
procesa las hojas es la que realiza el trabajo fundamental de devolver el dato 
en una lista. Las otras dos, que procesan los nodos internos, se limitan a 
concatenar los resultados de sus hijos en el orden correcto.

\lstinputlisting[linerange=46-49]{../Arbol23.hs}

\texttt{hojas arbolito1} debe devolver la cadena \verb+"abcdefghi"+.

\texttt{internos} tambi'en es un uso directo de un fold. La funci'on que procesa 
las hojas devuelve la lista vac'ia, pues solo queremos nodos internos, y las 
otras dos agregan su dato al principio de una lista que sigue con la 
concatenaci'on de los internos de sus hijos, logrando as'i el preorden.

\lstinputlisting[linerange=40-43]{../Arbol23.hs}

\verb+internos arbolito1+ debe devolver la lista \verb+[0,1,2,3,4,5,6,7]+.

La funci'on \texttt{esHoja} es muy simple, y solo hace pattern matching para 
detectar el constructor \texttt{Hoja a}, devolviendo \texttt{True} en ese caso y 
\texttt{False} en cualquier otro.

\lstinputlisting[linerange=51-53]{../Arbol23.hs}

\subsection*{Ejercicio 3}
\addcontentsline{toc}{subsection}{Ejercicio 3}
\texttt{mapA23} es la an'aloga a la funci'on \texttt{map} para listas. Toma dos 
funciones, una que transforma el dato de una hoja y otra que transforma el o los 
datos de los nodos internos. La escribimos usando un fold, donde cada funci'on 
construye la parte del 'arbol que le corresponde pero con los valores 
modificados por las funciones par'ametro.

\lstinputlisting[linerange=58-62]{../Arbol23.hs}

Un ejemplo de uso de esta funci'on podr'ia ser el siguiente:

\begin{verbatim}
incrementarHojas :: Num a => Arbol23 a b -> Arbol23 a b
incrementarHojas = mapA23 (+1) id
\end{verbatim}

Esta funci'on toma un 'arbol que almacena valores num'ericos en las hojas, y 
calcula otro 'arbol con la misma estructura, mismos nodos internos, pero cuyos 
valores de las hojas fueron incrementados en 1. Entonces la funci'on \verb+hojas (incrementarHojas arbolito2)+
tiene que devolver \verb+[0,1,-1,5]+.

\subsection*{Ejercicio 4}
\addcontentsline{toc}{subsection}{Ejercicio 4}
Para esta funci'on utilizamos \texttt{foldNat} tal como lo sugiere el enunciado.  
La idea es que para cada reemplazo y cada $n$ construimos una funci'on de 
'arboles en 'arboles que sabe truncarlos con ese reemplazo y al nivel $n$. El 
tipo de \texttt{foldNat} es \verb+b -> (b -> b) -> Integer -> b+. En nuestro 
caso, \texttt{b} es el tipo \verb+Arbol23 a b -> Arbol23 a b+, y as'i las 
funciones que debe recibir \texttt{foldNat} son m'as o menos claras.

Para $n=0$ no importa con qu'e 'arbol se eval'ue \texttt{truncar}, siempre hay 
que devolver una hoja con el reemplazo.

Para el caso recursivo, la idea es que a partir de una funci'on que sabe truncar 
'arboles al nivel $n$, hay que construir otra que sepa truncarlos en el nivel 
$n+1$, y eso es lo que hace la expresi'on lambda.  Dada una \texttt{f} de 
'arboles en 'arboles que sabe truncar a $n$, armamos otra funci'on que toma un 
'arbol (\texttt{ar}) y lo trunca a $n+1$. Para el caso de nodos internos, esto 
no es m'as que crear un 'arbol manteniendo la misma raiz, pero truncando sus 
hijos a nivel $n$ (usando \texttt{f}); y para el caso de hojas, como $n>0$, 
basta con dejarlas igual.

\lstinputlisting[linerange=75-81]{../Arbol23.hs}

El resultado de \verb+hojas (truncar 0 6 arbolito3)+ debe ser 
\verb+[1,2,3,2,3,4,3,4,5,4,5,6,0,0,0,0,0]+. Notar que \texttt{arbolito3} es un 
'arbol infinito.


\subsection*{Ejercicio 5}
\addcontentsline{toc}{subsection}{Ejercicio 5}
Otra aplicaci'on directa de \texttt{foldA23}, la idea es que las hojas contienen 
valores, con lo cual se les aplica la identidad. Los nodos internos de dos hijos 
tienen un operador, y entonces se le aplica ese operador al resultado de evaluar 
sus hijos. Lo mismo sucede con los nodos de tres hijos.

\lstinputlisting[linerange=92-95]{../Arbol23.hs}

El resultado de \verb+evaluar (truncar 0 6 arbolito3)+ debe ser $22$

\section{M'odulo Diccionario}

\subsection*{Ejercicio 6}
\addcontentsline{toc}{subsection}{Ejercicio 6}
Esta funci'on no precisa mucha explicaci'on. S'olo construye un diccionario 
usando la funci'on de comparaci'on suministrada.

\lstinputlisting[linerange=80-81]{../Diccionario.hs}

\subsection*{Ejercicio 7}
\addcontentsline{toc}{subsection}{Ejercicio 7}
Para esta funci'on utilizamos pattern matching sobre el diccionario. Si se 
encuentra vac'io, se construye uno nuevo que tiene como estructura el 'arbol que 
consiste de una 'unica hoja con la clave y el valor siendo definidos. En caso 
contrario, se crea uno nuevo pero usando como 'arbol el construido por la 
funci'on \texttt{insertar}.

\lstinputlisting[linerange=86-88]{../Diccionario.hs}

La funci'on \verb+estructura (definir 7 "Pumba" dicc1)+ debe devolver el 
siguiente 'arbol:

\begin{verbatim}
Just 2 9
    0
        (-10,"Chau")
        (0,"Hola")
    7
        (2,"etc.")
        (7,"Pumba")
    15
        (9,"a")
        (15,"Felicidades")
\end{verbatim}

\subsection*{Ejercicio 8}
\addcontentsline{toc}{subsection}{Ejercicio 8}
La idea de esta funci'on fue definir una auxiliar que maneja directamente el 
'arbol. Dicha funci'on es un \texttt{foldA23} que para el caso de las hojas 
verifica si la clave es la buscada y en caso afirmativo devuelve el valor, y en 
el caso de los nodos internos realiza la comparaci'on de la clave contra el o 
los datos del nodo para saber con qu'e resultado quedarse.

\lstinputlisting[linerange=93-106]{../Diccionario.hs}

La funci'on \verb+obtener (-10) dicc1+ debe devolver el string \verb+"Chau"+.

\subsection*{Ejercicio 9}
\addcontentsline{toc}{subsection}{Ejercicio 9}
Utilizamos pattern matching, devolviendo la lista vac'ia en el caso de que no 
haya 'arbol, y pasando \texttt{fst} por todos los datos de las hojas del 'arbol 
en caso contrario para quedarnos as'i con las claves.

\lstinputlisting[linerange=127-129]{../Diccionario.hs}

La funci'on \verb+claves dicc1+ debe devolver la lista \verb+[-10,0,2,9,15]+.


\subsection*{Ejercicio 10}
\addcontentsline{toc}{subsection}{Ejercicio 10}
Para resolver este ejercicio usamos una funci'on auxiliar, y otra muy auxiliar.  
La auxiliar toma un diccionario y un valor inicial, y genera una lista que es el 
camino que van marcando las pistas en ese diccionario, partiendo de ese valor.  
La lista siempre tendr'a un tesoro o una cola infinita de \texttt{Nothing}'s ya 
que sabemos por precondici'on que dado un diccionario y una pista, en una cantidad finita de pasos
se llega a un tesoro o se llega a una pista no definida (cuyo obtener da \texttt{Nothing}). 
La funci'on que calcula esta lista es la siguiente:

\lstinputlisting[linerange=16-20]{../Main.hs}

Una vez que se tiene eso, s'olo basta recorrer esa lista buscando el primer 
valor que sea tesoro. Si ning'un valor es tesoro se va a llegar a un 
\texttt{Nothing}, y en ese punto se sabr'a que el tesoro no se encontr'o. Para 
realizar esta b'usqueda usamos la funci'on \texttt{dropWhile}, que descarta 
elementos de una lista mientras se cumpla cierta condici'on, y devuelve todo el 
resto de la lista cuando encuentra el primero que no cumple. La funci'on de 
corte la hicimos auxiliar para que \texttt{busquedaDelTesoro} sea m'as clara. Es 
esta:

\lstinputlisting[linerange=24-26]{../Main.hs}

Es una funci'on muy sencilla que se usa para detectar un \texttt{Nothing} o un 
tesoro.

Una vez que tenemos esta lista, su primer elemento tiene que ser o un tesoro o 
\texttt{Nothing} (notar que esta lista sigue siendo infinita). Entonces para 
obtener el resultado final solo resta quedarnos con el primer valor y listo. En 
este punto es donde usamos fuertemente la evaluaci'on lazy de Haskell. La 
funci'on queda as'i:

\lstinputlisting[linerange=11-13]{../Main.hs}

\label{fin}

\end{document}
